1. Field of the Invention
The present invention relates generally to digital computers, and specifically to a pipelined central processing unit.
2. Description of Related Art
Pipelining is a proven method for enhancing the performance of the central processing unit (CPU) in a digital computer. In a pipelined CPU, multiple functional units concurrently execute the elementary operations for a plurality of instructions.
Computer systems often employ "virtual memory" techniques that allow programs to address more memory than is physically available. The portions of program or data that are not currently in use are stored in disk storage and are transferred when needed into physical memory. This loading of pages from disk when a nonresident memory location is accessed (i.e., when a "page fault" occurs) is called "demand paging."
In systems having virtual memory, a high speed associative memory called a "translation buffer" is often used to translate virtual addresses to the physical memory addresses. The translation buffer caches the most recently used virtual-to-physical address translations. If a desired translation is not present in the translation buffer (i.e., a translation buffer "miss"), the translation process must halt while the desired translation is read from a translation table in memory and loaded into the translation buffer. The construction and operation of the translation buffer is further described in Levy & Eckhouse, Jr., Computer Programming and Architecture--The VAX-11, Digital Equipment Corporation (1980) pp. 358-359.
In many computer systems, the execution of an instruction may cause an unusual condition called an "exception" to occur that causes the CPU to change the flow of control. Depending upon the instruction architecture, exceptions called "faults" may arise in the middle of execution for an instruction. In a computer system having virtual memory, for example, a "page fault" will occur during instruction operand fetching when the addressed operand does not reside in physical memory. In this case the current instruction cannot be completed, but it is desirable to use the CPU itself to carry out the demand paging to bring the desired operand from disk to physical memory.
When a "fault" occurs, the registers and memory are preserved so that the instruction can be restarted and produce the correct results after the fault condition is cleared. Therefore, the program counter is left pointing at the instruction that caused the fault.
In a pipelined processor, a fault causes the processing in the pipeline to be interrupted. Usually, everything that entered the pipeline before the instruction causing the fault is allowed to complete. Everything else that entered the pipeline later is prevented from completing, typically by clearing or flushing the respective stages of the pipeline.
In many pipelined processor designs, the control signals for the functional units are obtained from microinstructions issued by a microsequencer. In such a processor, several microinstructions may have partially executed when an exception condition is detected. In that case it is necessary to undo the effects of all those microinstructions. The most common technique used to deal with such situations is called a microtrap. Since microtraps relate closely to the micromachine execution, every processor has its own scheme to implement them. In every case, however, microtraps must permit the "roll back" of some number of microinstructions because the detection of a trap condition usually occurs quite late with respect to microinstruction execution.
A pipelined processor controlled by microinstructions is described in Sudhindra N. Mishra, "The VAX 8800 Microarchitecture," Digital Technical Journal, No. 4, February 1987, pp. 20-33. In the VAX 8800 processor, microtraps are implemented so that the offending microinstruction is allowed to complete, but subsequent microinstructions in the pipeline are blocked. Since the offending microinstruction may have caused some undesirable results, the trap handler microcode must fix the problem. Depending on the particular situation, either the microinstruction execution flow is resumed from the clocked state or a new flow is originated. A silo is generally used to save the state of the machine across a microtrap. In most cases the length of the silo is equal to the depth of pipelining. Since there are many more branch-condition bits than microaddress bits, it is more economical to save microaddresses in the trap silo than to save the conditions causing those addresses. During the execution of the trap routine, the trap silos are "frozen" (blocked from loading), thus saving the state of the micromachine at the time of trap.
In order to simplify the additional circuitry required for memory management, it is desirable to make use of the pipeline resources to resolve memory management faults such as a "page fault" or a "translation buffer miss." A memory management microroutine could be invoked as an interrupt as described above. In this case instructions having entered the pipeline before the instruction causing the trap would be completed and everything else having entered the pipeline later would be restored or backed up (with the program counter pointing to the instruction having caused the fault) prior to invocation of the memory management microroutine. Faults requiring invocation of system routines, for example, have been handled as macrocode interrupts.